//给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 
//
// 如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。 
//
// 从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。 
//
// 子数组 是数组中一个连续且可能为空的元素序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,2,3,1,3], k = 3
//输出：3
//解释：最优的方案是删除下标 2 和下标 4 的元素。
//删除后，nums 等于 [1, 3, 3, 3] 。
//最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
//可以证明无法创建更长的等值子数组。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,1,2,2,1,1], k = 2
//输出：4
//解释：最优的方案是删除下标 2 和下标 3 的元素。 
//删除后，nums 等于 [1, 1, 1, 1] 。 
//数组自身就是等值子数组，长度等于 4 。 
//可以证明无法创建更长的等值子数组。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// 1 <= nums[i] <= nums.length 
// 0 <= k <= nums.length 
// 
//
// Related Topics 数组 哈希表 二分查找 滑动窗口 👍 80 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author ldltd
 * @date 2024-05-23 14:57:25
 * @description 2831.找出最长等值子数组
 */
public class FindTheLongestEqualSubarray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindTheLongestEqualSubarray fun=new FindTheLongestEqualSubarray();
	 	 Solution solution = fun.new Solution();
		 System.out.println(solution.longestEqualSubarray(new ArrayList<>(Arrays.asList(4,1,5,4,3,5,5,4,8,5,5,8,3,8,6,2,7,4,8,3,3,8,3,2,5,5,6)), 3));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
		HashMap<Integer,List<Integer>> map=new HashMap<>();
		for (int i = 0; i < nums.size(); i++) {
			if(map.containsKey(nums.get(i))){
				map.get(nums.get(i)).add(i);
			}else {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				map.put(nums.get(i),list);
			}
		}
			int res=1;
		for (List<Integer> value : map.values()) {
			int l=0;
			int kt=k;
			for (int r = 1; r < value.size(); r++) {
				if(value.get(r)-value.get(r-1)-1>k) {
					l=r;
					kt=k;
					continue;
				}
				kt-=value.get(r)-value.get(r-1)-1;
				if(kt<0){
					while (l<r&&kt<0){
						l++;
						kt=Math.min(kt+value.get(l)-value.get(l-1)-1,k);
					}
				}
				res=Math.max(res,r-l+1);
			}
		}
		return  res;
    }
	/*
	* 每个元素统计一个列表，保存nums中的下标，
	* 对每个元素遍历，用滑动窗口
	* 则需要删去的元素为(pop[r]-pos[l]+1)-(r-l+1)
	* 如果大于K，右移左指针，直到小于等于k，同时更新k
	* 可以简化pos，保存pos[i]-i，则最后需要删除的个数为pos[r]-pos[l]*/
	public int longestEqualSubarray1(List<Integer> nums, int k) {
		int n = nums.size();
		List<Integer>[] posLists = new ArrayList[n + 1];
		Arrays.setAll(posLists, i -> new ArrayList<>());
		for (int i = 0; i < n; i++) {
			int x = nums.get(i);
			posLists[x].add(i - posLists[x].size());
		}

		int ans = 0;
		for (List<Integer> pos : posLists) {
			if (pos.size() <= ans) {
				continue; // 无法让 ans 变得更大
			}
			int left = 0;
			for (int right = 0; right < pos.size(); right++) {
				while (pos.get(right) - pos.get(left) > k) { // 要删除的数太多了
					left++;
				}
				ans = Math.max(ans, right - left + 1);
			}
		}
		return ans;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
